import random
from copy import copy

from checkers import games
from checkers import utils
from checkers import displays

class Piece(str): pass

# Some constants
V_RANGE = range(1, 9)
H_RANGE = [chr(a) for a in range(ord('A'), ord('I'))]
BLACK = Piece('B')
WHITE = Piece('W')
EMPTY = Piece(' ')

def promote(p):
    # Promote a piece to queen. We make a
    # copy to avoid sharing a reference.
    p = copy(p)
    p.queen = True
    return p

def queen(p):
    # Test if a piece is a queen
    return getattr(p, 'queen', False)

def initialize(board, clear=False):
    # Initialize a board with White on bottom
    # and Black on top, or initialize
    # a clear board.
    for i in V_RANGE:
        d = bool(i % 2)
        for j in H_RANGE:
            piece = (clear and EMPTY or
                     ((0 < i < 4) and WHITE or
                      (5 < i < 9) and BLACK or EMPTY))
            if d:
                board[(i, j)] = piece
                d = False
            else:
                d = True
    return board

def c_next(c, d):
    # Get the next char by delta.
    v = ord(c)
    return chr(v + d)

def valid_pos(v, h):
    # Check if a position is within the valid range.
    if v < V_RANGE[0] or v > V_RANGE[-1]:
        return False
    if h < H_RANGE[0] or h > H_RANGE[-1]:
        return False
    return True

def valid_pos_tuple(pos):
    # Same as valid_pos, except we take a tuple
    v, h = pos
    return valid_pos(v, h)

def recurse_eat(board, player, current, done=None):
    if done is None:
        done = []
    dn = 1
    dt = 2
    paths = []
    v, h = current
    # For normal pieces, we only look at the 4 surrounding
    # squares. If the first neighbor is a opponent, and
    # the second is a blank, then we can take the piece
    # and recurse from there.
    for move in ((1, -1), (1, 1), (-1, 1), (-1, -1)):
        next = map(lambda x: x * dn, move)
        next = v + next[0], chr(ord(h) + next[1])
        take = map(lambda x: x * dt, move)
        take = v + take[0], chr(ord(h) + take[1])
        # XXX Humm... we could improve this a bit
        if (valid_pos(*next) and valid_pos(*take)
            and next not in done
            and board[take] == EMPTY
            and board[next] not in (EMPTY, player)):
            done.append(next)
            n, steps, taken = recurse_eat(board, player, take, done[:])
            # After the recursion returns, we add the taken piece
            # to the returned set. Humm.... this reminds me of Prolog.
            n += 1
            taken = (next,) + taken
            steps = (take,) + steps
            paths.append((n, steps, taken))
    # The rulez sez: A player is forced to follow the
    # "Law of Majority" (sic), which means he is forced
    # to follow the path that takes most opposite pieces.
    paths.sort(lambda a, b: cmp(a[0], b[0]))
    return paths and paths[-1] or (0, (), ())

def queen_recurse_eat(board, player, current, done=None):
    if done is None:
        done = []
    # Instead of looking only at the surrounding positions,
    # we look all the way into each diagonal, until we find
    # (or not) an opposite player, and from there we try
    # to find a blank where we can land our queen.
    d_moves = queen_valid_moves(current)
    paths = []
    v, h = current
    for moves in d_moves:
        moves = map(lambda m, v=v, h=h: (v + m[0], c_next(h, m[1])), moves)
        moves = filter(valid_pos_tuple, moves)
        next = find_opponent(board, player, moves)
        # A piece may not be taken more than once
        if next is None or next in done:
            continue
        # Find empty squares past the opponent. Note
        # that there may be *none* (eg: when we found a
        # border, or there are more pieces past the opponent)
        moves = find_dest(board, next, moves)
        if not moves:
            continue
        done.append(next)
        # We try each valid destination because we may
        # find more paths where we can take pieces.
        for take in moves:
            n, steps, taken = queen_recurse_eat(board, player, take, done[:])
            n += 1
            taken = (next,) + taken
            steps = (take,) + steps
            paths.append((n, steps, taken))
    # As usual, return only the longest path
    paths.sort(lambda a, b: cmp(a[0], b[0]))
    return paths and paths[-1] or (0, (), ())

def find_opponent(board, player, moves):
    # Find the first position where there's an
    # opponent in the given list of moves.
    other = player == BLACK and WHITE or BLACK
    for move in moves:
        if board[move] == other:
            return move
    return None

def find_dest(board, current, moves):
    # Given a starting position, find
    # the valid destinations (eg: the
    # ones which are empty, up to finding
    # a non-empty one, or a border)
    start = moves.index(current) + 1
    dest = []
    for move in moves[start:]:
        if board[move] == EMPTY:
            dest.append(move)
        else:
            break
    return dest

def valid_moves(board, to_move):
    # Compute the valid moves for a
    # given player.
    # A move is represented by a tuple with
    # the following information:
    # current -- Starting position (v, h)
    # dest -- Ending position (v, h)
    # steps -- List of steps needed to get
    #          from ``current`` to ``dest``
    # taken -- List of positions of opponent
    #          pieces that were taken by this move
    locs = []
    valid = []
    # First we find all the pieces
    # of this player.
    for k, v in board.items():
        if v == to_move:
            locs.append(k)
    d = to_move == WHITE and 1 or -1
    take = False
    # Then for each of those positions, we
    # check if th player can move to an empty
    # square, or if the player is allowed to
    # takeover pieces from the opponent.
    for v, h in locs:
        current = (v, h)
        q = queen(board[current])
        if not q:
            # Normal pieces move diagonally
            # one square at a time. They can
            # only move forward when in non-taking
            # mode.
            d_moves = ([(d, 1)], [(d, -1)])
        else:
            d_moves = queen_valid_moves(current)
        # d_moves is a list of directions, and for
        # each direction, a list of tentative deltas
        # from the origination position.
        for moves in d_moves:
            # We map the deltas to real positions from the
            # original position
            moves = map(lambda m, v=v, h=h: (v + m[0], c_next(h, m[1])), moves)
            # And then filter out the invalid ones
            moves = filter(valid_pos_tuple, moves)
            for move in moves:
                if board[move] == EMPTY:
                    valid.append((current, move, (), ()))
                else:
                    # Found a non-empty value. Stop walking through
                    # list of valid moves.
                    break
        if not q:
            n, steps, taken = recurse_eat(board, to_move, current)
        else:
            # Queens can walk more than one square at a time, so we
            # made a separate version of recurse_eat to make the code
            # simpler.
            n, steps, taken = queen_recurse_eat(board, to_move, current)
        if n:
            take = True
            valid.append((current, steps[-1], steps, taken))
    if take:
        # If there's at least one move which that we can takeover
        # a piece, then filter out the ones which we can't take any
        # piece. The rules say we are forced to takeover in
        # this case, so filtering out the non-taking moves
        # makes the search narrower.
        valid = filter(lambda move: len(move[3]) > 0, valid)
    return valid

def queen_valid_moves(current):
    v, h = current
    # The four directions
    directions = ((1, -1), (1, 1), (-1, 1), (-1, -1))
    # Get the minimum distance to top
    a = min(V_RANGE[-1] - v, ord(H_RANGE[-1]) - ord(h))
    # The minimum distance to bottom
    b = min(v - V_RANGE[0], ord(h) - ord(H_RANGE[0]))
    # And then the max of both
    r = max(a, b)
    moves = []
    # And finally, build a list of deltas in this range
    for d in directions:
        m = []
        moves.append(m)
        nv, nh = d
        for i in range(1, r + 1):
            m.append((nv * i, nh * i))
    return moves

def promotes(board, piece, move):
    # Tests if a piece will be promoted
    # with a given move.
    v, h = move
    if (not queen(board[move]) and
        (v == 8 and piece == WHITE) or
        (v == 1 and piece == BLACK)):
        return True
    return False

class Checkers(games.Game):

    def __init__(self, to_move, out=displays.StdOut()):
        self.out = out
        board = {}
        initialize(board)
        moves = valid_moves(board, to_move)
        self.initial = utils.Struct(to_move=to_move, utility=0,
                                    board=board, moves=moves)

    def make_move(self, move, state):
        if move not in state.moves:
            raise ValueError, 'Invalid move %r' % move
        current, dest, steps, taken = move
        board = state.board.copy()
        v, h = dest
        piece = board[current]
        # Check if the piece can be promoted,
        # and then promote it.
        if promotes(board, piece, dest):
            piece = promote(piece)
        # Move the piece, setting it's original
        # position to empty
        board[dest] = piece
        board[current] = EMPTY
        # Then, if any piece has been taken
        # by this move, remove the pieces from the
        # board by setting the position to empty
        for take in taken:
            board[take] = EMPTY
        # Alternate the players
        to_move = state.to_move == BLACK and WHITE or BLACK
        moves = valid_moves(board, to_move)
        return utils.Struct(to_move=to_move,
                            utility=self.compute_utility(move, state),
                            board=board, moves=moves)

    def terminal_test(self, state):
        # A terminal test occurs when there are
        # no more valid moves for a given state
        return not self.legal_moves(state)

    def legal_moves(self, state):
        # Legal moves for a given state
        return state.moves

    def utility(self, state, player):
        # The utility is a number representing a
        # value which is the suggested score for the
        # move originating that state.
        return state.utility

    def display(self, state):
        self.out.display(self, state)

    def display_move(self, move, state):
        # Display the move.
        # By default we print the label for the
        # player, the originating and destination
        # positions (may be a list) and a 'X' if
        # the move took any pieces from the opponent
        print '%s:' % state.to_move,
        current, dest, steps, taken = move
        if steps:
            for step in steps:
                print '%s%s-%s%s ' % (current[0], current[1],
                                      step[0], step[1]),
                current = step
            print 'X',
        else:
            print '%s%s-%s%s ' % (current[0], current[1], dest[0], dest[1]),
        print '\n'

    def compute_utility(self, move, state):
        # Compute a suggestion score for a given move
        # to help deciding which moves are better than
        # others. This is the heart of a good engine.
        to_move = state.to_move
        other = to_move == BLACK and WHITE or BLACK
        board = state.board
        # All pieces were taken. End of game, maximum value.
        if not board.values().count(other):
            return to_move == WHITE and infinity or -infinity
        curr, to, steps, takes = move
        v, h = to
        b = 0
        # If the destination square is in one of the sides,
        # it is impossible for someone to take our piece. This
        # is a good move.
        if h in (H_RANGE[0], H_RANGE[-1]):
            b += 4
        if h in (H_RANGE[1], H_RANGE[-2]):
            b += 2
        piece = board[curr]
        # If a move will promote our piece to a queen
        # then this is a very good move.
        if promotes(board, piece, to):
            b += 8
        # Delta so we compute the score negatively
        # for the White player.
        d = to_move == WHITE and 1 or -1
        # Taking a queen is a great move too! We multiply
        # the number of queens taken by 4.
        queens = [take for take in takes if queen(board[take])]
        return (len(takes) * 4 + len(queens) * 8 + b) * d
